package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/08/17 18:34
 **/
public class Day32_3_Num63_UniquePathsWithObstacles {
    public static void main(String[] args) {
        int[][] arr = new int[3][3];
        arr[1][1] = 1;
        int[][] arr1 = new int[2][2];
        arr1[0][1] = 1;
        int[][] arr2 = new int[1][1];
        arr2[0][0] = 1;
        int[][] arr3 = new int[3][2];
        arr3[1][0] = 1;arr3[1][1] = 1;
        System.out.println(uniquePathsWithObstacles(arr3));;
    }

    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
        for (int i = 0; i < n && obstacleGrid[0][i] == 0; i++) dp[0][i] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

//    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
//        for (int i = 0; i < obstacleGrid.length; i++) {
//            for (int j = 0; j < obstacleGrid[0].length; j++) {
//                if(obstacleGrid[i][j] == 1) obstacleGrid[i][j] = -1;
//            }
//        }
//        for(int i = 1;i < obstacleGrid.length;i++){
//            if(obstacleGrid[i][0] == -1) {
//                obstacleGrid[i][0] = 0;
//                continue;
//            }
//            obstacleGrid[i][0] = 1;
//        }
//        for (int i = 0; i < obstacleGrid[0].length; i++) {
//            if(obstacleGrid[0][i] == -1) {
//                obstacleGrid[0][i] = 0;
//                continue;
//            }
//            obstacleGrid[0][i] = 1;
//        }
//        for (int i = 1; i < obstacleGrid.length; i++) {
//            for (int j = 1; j < obstacleGrid[0].length; j++) {
//                if(obstacleGrid[i][j] == -1) {
//                    obstacleGrid[i][j] = 0;
//                    continue;
//                }
//                obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1];
//                //System.out.println(i+" "+j+" "+ obstacleGrid[i][j] +" = "+obstacleGrid[i-1][j]+" + "+obstacleGrid[i][j-1]);
//            }
//        }
//        return obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1];
//    }
}